//给定一个二叉树，检查它是否是镜像对称的。 
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 1592 👎 0

package com.cute.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class SymmetricTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(4);
        root.left = node1;root.right = node2;node1.left = node3;node1.right = node4;node2.left = node5;node2.right = node6;
        boolean res = new SymmetricTree().new Solution().isSymmetric(root);

    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 遍历树的时候使用栈，左右子树使用不同的遍历方法？
     */
    public boolean isSymmetric1(TreeNode root) {
        if (root == null) return true;
        return dfs(root.left, root.right);
    }
    public boolean dfs(TreeNode left, TreeNode right){
        if (left == null && right == null) return true; // 两个节点都为null 返回true
        if (left == null || right == null) return false; // 两个节点不都为null 返回false
        if (left.val != right.val ) return false; //此时两个节点都不为null，判断值是否相同，不相同再返回
        return dfs(left.left, right.right)&&dfs(left.right, right.left);//递归调用
    }


    /**
     * 使用层序遍历来实现对称的判断，队列中元素添加顺序合适的话会很大程度上优化空间
     */
    public boolean isSymmetric(TreeNode root) {
        /*Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null) queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            if (size!=1 && (size&1) == 1) return false;
            TreeNode[] nodes = new TreeNode[size];
            for (int i = 0; i < size; i++){
                nodes[i] = queue.poll();
                if(nodes[i].left!=null) queue.add(nodes[i].left);
                if(nodes[i].right!=null) queue.add(nodes[i].right);
            }
            int i = 0;
            int j = size-1;
            while (i<=j){
                if (nodes[i].left!=null && nodes[j].right!=null){
                    if (nodes[i].left.val != nodes[j].right.val) return false;
                }else if(!(nodes[i].left==null && nodes[j].right==null)) return false;
                if (nodes[i].right!=null && nodes[j].left!=null){
                    if (nodes[i].right.val != nodes[j].left.val) return false;
                }else if(!(nodes[i].right==null && nodes[j].left==null)) return false;
                i++;j--;
            }

        }
        return true;*/
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        while (!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;
            //能到这里说明left和right都不为null了
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
















































